Method: miniMax(int, double, double)

1: package de.fhdw.gaming.ipspiel22.searchtree.algorithm;
2:
3: import java.util.LinkedHashMap;
4: import java.util.List;
5: import java.util.Map;
6: import java.util.Optional;
7: import de.fhdw.gaming.core.domain.GameException;
8: import de.fhdw.gaming.core.domain.Move;
9: import de.fhdw.gaming.core.domain.Player;
10: import de.fhdw.gaming.core.domain.State;
11: import de.fhdw.gaming.ipspiel22.searchtree.domain.MinMaxGame;
12:
13: /**
14: * MinMax algorithm implementation.
15: *
16: * @param <P> The type of player.
17: * @param <S> The type of state.
18: * @param <M> The type of move.
19: * @param <G> The type of object implementing the {@link MinMaxGame} interface.
20: */
21: public final class MinMaxAlgorithm<P extends Player<P>, S extends State<P, S>, M extends Move<P, S>,
22: G extends MinMaxGame<P, S, M>> {
23: /**
24: * Variable for the class with the necessary functions.
25: */
26: private final G game;
27:
28: /**
29: * Constructs an object of this class.
30: *
31: * @param game The interface to the underlying game.
32: */
33: public MinMaxAlgorithm(final G game) {
34: this.game = game;
35: }
36:
37: /**
38: * Returns the best move for the current player.
39: *
40: * @param depth The search depth.
41: */
42: public Optional<M> getBestMove(final int depth) throws GameException {
43: if (this.game.isGameOver()) {
44: return Optional.empty();
45: }
46: final Map<M, Double> scores = new LinkedHashMap<>();
47: for (final M move : this.game.getPossibleMoves()) {
48: this.game.commitMove(move);
49: this.game.saveFirstMoves(move);
50: scores.put(move, -this.miniMax(depth, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY));
51: this.game.rollbackMove(move);
52: }
53: return scores.entrySet().stream().max((e1, e2) -> e1.getValue().compareTo(e2.getValue()))
54: .map(Map.Entry::getKey);
55: }
56:
57: /**
58: * MinMax algorithm which calculates the best next move.
59: *
60: * @param depth the depth of searching (moves in the future).
61: * @param alpha alpha value for alpha-beta pruning (on first call: -inf).
62: * @param beta beta value for alpha-beta pruning (on first call: +inf).
63: * @return the value for the next move.
64: */
65: public double miniMax(final int depth, final double alpha, final double beta) throws GameException {
66:• if (depth == 0 || this.game.isGameOver()) {
67: return this.game.evaluateStateful();
68: }
69: double maxWert = alpha;
70: final List<M> moves = this.game.getPossibleMoves();
71:• for (final M move : moves) {
72: this.game.commitMove(move);
73: final double wert = -this.miniMax(depth - 1, -beta, -maxWert);
74: this.game.rollbackMove(move);
75:• if (wert > maxWert) {
76: maxWert = wert;
77:• if (maxWert >= beta) {
78: break;
79: }
80: }
81: }
82: return maxWert;
83: }
84: }